//
// Created by francklinson on 2021/7/7.
//
//
//有一个二维矩阵 grid，每个位置要么是陆地（记号为0 ）要么是水域（记号为1 ）。
//
//我们从一块陆地出发，每次可以往上下左右4 个方向相邻区域走，能走到的所有陆地区域，我们将其称为一座「岛屿」。
//
//如果一座岛屿完全由水域包围，即陆地边缘上下左右所有相邻区域都是水域，那么我们将其称为 「封闭岛屿」。
//
//请返回封闭岛屿的数目。
//
//来源：力扣（LeetCode）
//链接：https://leetcode-cn.com/problems/number-of-closed-islands
//著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

#include <vector>
#include <iostream>
#include <functional>
#include <queue>

using namespace std;

class Solution {
public:
    /**
     * 判断一块陆地是否会接触到边界 dfs
     * @param grid
     * @return
     */
    int closedIsland(vector<vector<int>> &grid) {
        int Row = (int) grid.size();
        if (Row == 0)
            return 0;
        int Col = (int) grid[0].size();
        function<bool(int, int)> dfs = [&](int r, int c) {
            if (!(0 <= r && r < Row && 0 <= c && c < Col))    //这一步超出二维矩阵了。说明上一步在边缘
                return true;
            if (grid[r][c] != 0)    //非陆地。海洋，或者已经访问过了
                return false;
            grid[r][c] = 6666;     //就不用单开visited数组了（只要不是0，想赋几赋几）
            bool flag = false;
            /// attention:必须4个方向遍历完。把这个岛屿mark完整!!!!!!!!
            for (auto x : vector<pair<int, int>>{{r - 1, c},
                                                 {r + 1, c},
                                                 {r,     c - 1},
                                                 {r,     c + 1}}) {
                int nr = x.first;
                int nc = x.second;
                if (dfs(nr, nc) == true) //只有要有一个方向碰到了矩形的边，这个岛就是碰到了，就不是封闭的
                    flag = true; /// 岛屿要标记完，不能直接return
            }
            return flag;

        };
        /// 思路：任何一个岛屿。只要碰到二维矩阵的边了。就不是封闭的。
        int res = 0;
        for (int r = 0; r < Row; r++)
            for (int c = 0; c < Col; c++)
                if (grid[r][c] == 0)
                    if (dfs(r, c) == false)
                        res++;
        return res;
    }
};

class Solution2 {
public:
    /**
     * 判断一块陆地是否会接触到边界 bfs
     * @param grid
     * @return
     */
    int closedIsland(vector<vector<int>> &grid) {
        int Row = (int) grid.size();
        if (Row == 0)
            return 0;
        int Col = (int) grid[0].size();
        function<bool(int, int)> bfs = [&](int r, int c) {
            if (grid[r][c] != 0) return true;
            queue<pair<int, int>> q;
            q.emplace(r, c);
            bool flag = true;
            while (!q.empty()) {
                auto p = q.front();
                q.pop();
                grid[p.first][p.second] = 1; /// 标记
                for (auto nextPos:vector<pair<int, int>>{{p.first - 1, p.second},
                                                         {p.first + 1, p.second},
                                                         {p.first,     p.second - 1},
                                                         {p.first,     p.second + 1}}) {
                    int nr = nextPos.first;
                    int nc = nextPos.second;
                    if (!(0 <= nr && nr < Row && 0 <= nc && nc < Col)) {
                        flag = false;
                        continue;
                    }
                    if (grid[nr][nc] == 0)
                        q.emplace(nr, nc);
                }
            }
            return flag;

        };
        /// 思路：任何一个岛屿。只要碰到二维矩阵的边了。就不是封闭的。
        int res = 0;
        for (int r = 0; r < Row; r++)
            for (int c = 0; c < Col; c++)
                if (grid[r][c] == 0)
                    if (bfs(r, c))
                        res++;
        return res;
        // 比较慢
    }
};

int main() {
    vector<vector<int>> grid{{1, 1, 1, 1, 1, 1, 1, 0},
                             {1, 0, 0, 0, 0, 1, 1, 0},
                             {1, 0, 1, 0, 1, 1, 1, 0},
                             {1, 0, 0, 0, 0, 1, 0, 1},
                             {1, 1, 1, 1, 1, 1, 1, 0}};
    Solution2 sol;
    cout << sol.closedIsland(grid) << endl;
    vector<int> as{3, 4};
    return 0;
}
